package com.zhanghp.class037;

import com.zhanghp.common.TreeNode;

/**
 * 普通二叉树上寻找两个节点的最近公共祖先<br/>
 * 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 *
 * @author zhanghp
 * @since 2024/4/19 14:43
 */
public class Code01_LowestCommonAncestor {

    static class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root ==null || root == p || root == q){
                return root;
            }
            TreeNode lNode = lowestCommonAncestor(root.left, p, q);
            TreeNode rNode = lowestCommonAncestor(root.right, p, q);
            // 左右孩子，没找到关于p和q
            if (lNode == null && rNode == null) {
                return null;
            }
            // 左右孩子都找到了，所以root为塔里的共同祖先（递归会到最细粒度，然后开始条件判断，所以此时找到，就是最近的祖先）
            if (lNode !=null && rNode != null) {
                return root;
            }
            // 兜底：说明lNode或rNode有一个为空，有一个不为空
            return lNode == null ? rNode : lNode;
        }
    }

}
